public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().maxSubArray1(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}


// ------------- 第二次做 ----------------
class Solution {
    //O(n)动态规划
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];         //当前的最大长度
        int preMaxSum = nums[0];      //以当前i为结尾的子序列最大长度
        for (int i = 1; i < nums.length; i++) {
            preMaxSum = Math.max(nums[i], preMaxSum + nums[i]);
            maxSum = Math.max(maxSum, preMaxSum);
        }
        return maxSum;
    }

    //递归法（线段树）

    class Status {
        int lSum;
        int rSum;
        int mSum;
        int iSum;

        Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }
    public int maxSubArray1(int[] nums) {
        Status status = getStatus(nums, 0, nums.length - 1);
        return status.mSum;
    }

    Status getStatus(int[] nums, int l, int h) {
        if (l == h) {
            return new Status(nums[l], nums[l], nums[l], nums[l]);
        }

        int m = (l + h) / 2;
        Status lStatus = getStatus(nums, l, m);
        Status rStatus = getStatus(nums, m + 1, h);
        return mergeStatus(lStatus, rStatus);
    }

    Status mergeStatus(Status lStatus, Status rStatus) {
        return new Status(
                Math.max(lStatus.lSum, lStatus.iSum + rStatus.lSum),
                Math.max(rStatus.rSum, lStatus.rSum + rStatus.iSum),
                Math.max(lStatus.rSum + rStatus.lSum, Math.max(lStatus.mSum, rStatus.mSum)),
                lStatus.iSum + rStatus.iSum
        );
    }
}

// ------------- 第一次做 ----------------
//不通过
class Solution1 {
    public int maxSubArray(int[] nums) {
        int i = 0;
        int max = -100000;
        while (i < nums.length && nums[i] < 0) {
            max = Math.max(nums[i], max);
            i++;
        }
        if (i == nums.length) {
            return max;
        }

        int subArraySum = 0;
        int maxSubArraySum = 0;
        while (i < nums.length) {
            while (i < nums.length && nums[i] >= 0) {
                subArraySum += nums[i];
                if (subArraySum > maxSubArraySum) {
                    maxSubArraySum = subArraySum;
                }
                i++;
            }
            while (i < nums.length && nums[i] < 0) {
                subArraySum += nums[i];
                i++;
            }
            if (subArraySum < 0) {
                subArraySum = 0;
            }
        }
        return maxSubArraySum;
    }
}

//动态规划
class Solution11 {
    public int maxSubArray(int[] nums) {
        int preMaxSum = 0;
        int maxSum = -1000000;
        for (int each : nums) {
            preMaxSum = Math.max(preMaxSum + each, each);
            maxSum = Math.max(preMaxSum, maxSum);
        }
        return maxSum;
    }
}

//分治
class Solution12 {
    static class Status {
        int iSum, lSum, rSum, mSum;
        Status(int iSum, int lSum, int rSum, int mSum) {
            this.iSum = iSum;
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return divideAndComquer(nums, 0, nums.length - 1).mSum;
    }

    private Status divideAndComquer(int[] nums, int l, int r) {
        if (l == r) {
            return new Status(nums[l], nums[l], nums[l], nums[l]);
        }
        int m = (l + r) >> 1;
        Status lStatus = divideAndComquer(nums, l, m);
        Status rStatus = divideAndComquer(nums, m + 1, r);
        return merge(lStatus, rStatus);
    }

    private Status merge(Status lStatus, Status rStatus) {
        int iSum = lStatus.iSum + rStatus.iSum;
        int lSum = Math.max(lStatus.lSum, lStatus.iSum + rStatus.lSum);
        int rSum = Math.max(rStatus.rSum, lStatus.rSum + rStatus.iSum);
        int mSum = Math.max(Math.max(lStatus.mSum, rStatus.mSum), lStatus.rSum + rStatus.lSum);
        return new Status(iSum, lSum, rSum, mSum);
    }
}